#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_V 10 // 最大顶点数

// 邻接表结点结构
typedef struct AdjListNode
{
    int vertex;               // 邻接顶点索引
    struct AdjListNode *next; // 指向下一个邻接结点
} AdjListNode;

// 顶点结构
typedef struct
{
    char *name;        // 顶点名称
    AdjListNode *head; // 邻接表头指针
} Vertex;

// 图结构（邻接表）
typedef struct
{
    Vertex vertices[MAX_V]; // 顶点数组
    int vCount;             // 当前顶点数
} Graph;

// 1. 创建图
Graph *createGraph()
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->vCount = 0;

    // 初始化顶点数组
    for (int i = 0; i < MAX_V; i++)
    {
        g->vertices[i].name = NULL;
        g->vertices[i].head = NULL;
    }
    return g;
}

// 2. 添加顶点
void addVertex(Graph *g, const char *name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    g->vertices[g->vCount].name = strdup(name);
    g->vCount++;
}

// 3. 添加边（有向图）
void addEdge(Graph *g, int from, int to)
{
    if (from < 0 || from >= g->vCount || to < 0 || to >= g->vCount)
    {
        printf("Error: Invalid vertex index\n");
        return;
    }

    // 仅添加单向边（from→to）
    AdjListNode *newNode = (AdjListNode *)malloc(sizeof(AdjListNode));
    newNode->vertex = to;
    newNode->next = g->vertices[from].head;
    g->vertices[from].head = newNode;
}

// 4. 打印图
void printGraph(Graph *g)
{
    printf("Adjacency List (Directed Graph):\n");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%s: ", g->vertices[i].name);
        AdjListNode *node = g->vertices[i].head;
        while (node)
        {
            printf("%s -> ", g->vertices[node->vertex].name);
            node = node->next;
        }
        printf("NULL\n");
    }
}

// 5. 销毁图
void destroyGraph(Graph *g)
{
    if (!g)
        return;

    // 释放每个顶点的邻接表
    for (int i = 0; i < g->vCount; i++)
    {
        free(g->vertices[i].name);

        AdjListNode *node = g->vertices[i].head;
        while (node)
        {
            AdjListNode *temp = node;
            node = node->next;
            free(temp);
        }
    }

    // 释放图结构
    free(g);
}

int main()
{
    // 创建图
    Graph *g = createGraph();

    // 添加顶点
    addVertex(g, "A");
    addVertex(g, "B");
    addVertex(g, "C");
    addVertex(g, "D");

    // 添加有向边
    addEdge(g, 0, 1); // A→B
    addEdge(g, 0, 2); // A→C
    addEdge(g, 1, 3); // B→D
    addEdge(g, 2, 3); // C→D
    addEdge(g, 3, 0); // D→A (形成环)

    // 打印图
    printGraph(g);

    // 销毁图
    destroyGraph(g);

    return 0;
}